import java.util.*;


// 数组（旋转数组），二分查找，双指针
class Solution2 {
    public int minNumberInRotateArray (int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(array[mid] > array[right])
                left = mid + 1;
                //无法判断，一个一个试
            else if(array[mid] == array[right])
                right--;
                //最小数字要么是mid要么在mid左边
            else
                right = mid;
        }
        return array[left];
    }
}

// 二维数组（行列各自递增数组），利用题目的递增条件，提高查找效率，一次排除一行或者一列
class Solution1 {
    public boolean Find (int target, int[][] array) {
        int i = 0;
        int j = array[0].length - 1;
        while (i < array.length && j >= 0) {
            if (target > array[i][j]) {
                i++;
            } else if (target < array[i][j]) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
}
